// 顺序栈
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1

#define LONGTH 5

typedef int Status;
typedef int ElemType;

// 顺序栈的类型
typedef struct
{
    ElemType *elem;
    int top;       // 最后进栈元素的索引+1
    int size;      // 栈的大小
    int increment; // 每次扩容增加的大小
} SqStack;

// 初始化顺序栈
Status InitStack_Sq(SqStack &S, int size, int inc)
{
    S.elem = (ElemType *)malloc(size * sizeof(ElemType));
    if (NULL == S.elem)
        return OVERFLOW;
    S.top = 0;
    S.size = size;
    S.increment = inc;
    return OK;
}

// 销毁顺序栈
Status DestoryStack_Sq(SqStack &S)
{
    free(S.elem);
    S.elem = NULL;
    return OK;
}

// 判断S 是否空，若空则返回TRUE，否则返回FALSE
Status StackEmpty_Sq(SqStack S)
{
    if (0 == S.top)
        return TRUE;
    return FALSE;
}

// 清空栈S
void ClearStack_Sq(SqStack &S)
{
    if (0 == S.top)
        return;
    S.size = 0;
    S.top = 0;
}

// 元素e压入栈S
Status Push_Sq(SqStack &S, ElemType e)
{
    ElemType *newbase;
    if (S.top >= S.size)
    {
        // 申请新的空间
        newbase = (ElemType *)realloc(S.elem, (S.size + S.increment) * sizeof(ElemType));
        if (NULL == newbase)
            return OVERFLOW;
        S.elem = newbase;
        S.size += S.increment;
    }
    S.elem[S.top++] = e;
    return OK;
}

// 取栈S的栈顶元素，并用e返回
Status GetTop_Sq(SqStack S, ElemType &e)
{
    if (0 == S.top)
        return ERROR;
    e = S.elem[S.top - 1];
    return e;
}

// 栈顶元素出栈，并用e返回
Status Pop_Sq(SqStack &S, ElemType &e)
{
    // 注意！SqStack &S一开始没加&就错了，要小心！传引用！
    if (0 == S.top)
        return ERROR;
    e = S.elem[S.top - 1];
    S.top--;
    return e;
}

int main()
{
    SqStack S;
    int size, increment, i;
    size = LONGTH;
    increment = LONGTH;
    ElemType e, eArray[LONGTH] = {1, 2, 3, 4, 5};
    //显示测试值
    printf("---【顺序栈】---\n");
    printf("栈S的size为：%d\n栈S的increment为：%d\n", size, increment);
    printf("待测试元素为：\n");
    for (i = 0; i < LONGTH; i++)
    {
        printf("%d\t", eArray[i]);
    }
    printf("\n");

    //初始化顺序栈
    if (!InitStack_Sq(S, size, increment))
    {
        printf("初始化顺序栈失败\n");
        exit(0);
    }
    printf("已初始化顺序栈\n");

    //入栈
    for (i = 0; i < S.size; i++)
    {
        if (!Push_Sq(S, eArray[i]))
        {
            printf("%d入栈失败\n", eArray[i]);
            exit(0);
        }
    }
    printf("已入栈\n");

    //判断非空
    if (StackEmpty_Sq(S))
        printf("S栈为空\n");
    else
        printf("S栈非空\n");

    //取栈S的栈顶元素
    printf("栈S的栈顶元素为：\n");
    printf("%d\n", GetTop_Sq(S, e));

    //栈S元素出栈
    printf("栈S元素出栈为：\n");
    for (i = 0, e = 0; i < S.size; i++)
    {
        printf("%d\t", Pop_Sq(S, e));
    }
    printf("\n");

    //清空栈S
    ClearStack_Sq(S);
    printf("已清空栈S\n");

    return 0;
}